Heretofore, a technique has been known for determining deterioration of a catalyst (hereinafter simply referred to as “catalyst”) that purifies exhaust gas of an internal combustion engine, and Japanese Patent Application Publication No. 2007-285288 discloses a deterioration determination system proposed by the present applicant, for example. In the deterioration determination system, first and second oxygen concentration sensors are respectively provided on the upstream side and downstream side of a three-way catalyst, and oxygen inflow into the three-way catalyst is calculated on the basis of an intake air volume and oxygen concentration detected by the first oxygen concentration sensor. Additionally, air-fuel ratio switching control (perturbation control) is performed to alternately switch the air-fuel ratio of an air-fuel mixture to the rich side and lean side of the stoichiometric air-fuel ratio, according to a result of comparison between the calculated oxygen inflow and its target value. Then, it is determined that the three-way catalyst is deteriorated when output of the second oxygen concentration sensor fluctuates largely during the air-fuel ratio switching control.